package main

import "fmt"

func main() {
	nums := []int{1,3,-1,-3,5,3,6,7}
	k := 3
	fmt.Println(maxSlidingWindow(nums, k))
}

/**
思路：
1. 使用一个递减的双端队列，队头最大，队尾最小
2. 如果大于等于队列的最后一个元素，就把队尾的元素去除，直到队列为空或者队尾元素大于当前元素，再把当前元素追加到队尾
3. 窗口满了后，每次都能得到该窗口的最大值，即队头元素
 */
func maxSlidingWindow(nums []int, k int) []int {
	result := make([]int, len(nums) - k + 1)
	win := make([]int, 0, len(nums))

	for idx := range nums{
		for len(win) != 0 && nums[idx] >= nums[win[len(win)-1]] {
			win = win[:len(win) - 1]
		}

		// 元素入队尾
		win = append(win, idx)

		// 队头最大的元素离开滑动窗口
		if idx - win[0] >= k {
			win = win[1:]
		}

		// 窗口满了后，每次都能得到该窗口的最大值，即队头元素
		if idx >= (k - 1){
			result[idx - k + 1] = nums[win[0]]
		}
	}

	return result
}
